package 链表;

import java.util.ArrayList;
import java.util.List;

public class NC40两个链表生成相加链表 {

    /**
     * 假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
     * 给定两个这种链表，请生成代表两个整数相加值的结果链表。
     * 例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
     */

    public ListNode addInList (ListNode head1, ListNode head2) {

        List<Integer> list1=new ArrayList<>();
        List<Integer> list2=new ArrayList<>();

        while (head1!=null||head2!=null){
            if(head1!=null) {
                list1.add(head1.val);
                head1=head1.next;
            }
            if(head2!=null){
                list2.add(head2.val);
                head2=head2.next;
            }
        }

        int carryNum=0;
        List<Integer> list=new ArrayList<>();
        for (int i = list1.size()-1,j=list2.size()-1; i >=0 && j>=0 ; i--,j--) {
            int num1=list1.get(i);
            int num2=list2.get(j);
            int sum=num1+num2+carryNum;
            carryNum=sum/10;
            list.add(sum%10);
        }

        if(list1.size()>list2.size()){
            for (int i = list1.size()-list2.size()-1; i >= 0; i--) {
                int num1=list1.get(i);
                int sum=num1+carryNum;
                carryNum=sum/10;
                list.add(sum%10);
            }
        }else{
            for (int i = list2.size()-list1.size()-1; i >= 0; i--) {
                int num1=list2.get(i);
                int sum=num1+carryNum;
                carryNum=sum/10;
                list.add(sum%10);
            }
        }

        if(carryNum!=0){
            list.add(carryNum);
        }

        ListNode listNode=new ListNode(-1);
        ListNode cur=listNode;
        for (int i = list.size()-1; i >= 0; i--) {
            cur.next=new ListNode(list.get(i));
            cur=cur.next;
        }

        return listNode.next;
    }

    public static void main(String[] args) {
        ListNode listNode1 = ListNode.createListNode(new int[]{9, 3, 7});
        ListNode listNode2 = ListNode.createListNode(new int[]{6, 3});
        NC40两个链表生成相加链表 n=new NC40两个链表生成相加链表();
        ListNode result = n.addInList(listNode1, listNode2);
        ListNode.printListNode(result);
    }

}
